DAY 19 試題

問題描述

給定一個包含 k 個鏈結串列的陣列，每個鏈結串列都已經按照升序排序。請將所有鏈結串列合併為一個排序後的鏈結串列，並返回這個合併後的鏈結串列。

例1：

• 輸入：lists = [[1,4,5],[1,3,4],[2,6]] 輸出：[1,1,2,3,4,4,5,6]

  解釋：

• 鏈結串列為：1->4->5，1->3->4，2->6

• 合併後結果：1->1->2->3->4->4->5->6

例2：

• 輸入：lists = [] 輸出：[]

例3：

• 輸入：lists = [[]] 輸出：[]

解題思路

本題的核心是將 k 個已排序的鏈結串列合併為一個排序後的鏈結串列。可以使用最小堆或優先佇列來進行高效的合併操作。
具體思路如下：

1. 初始化最小堆：將每個鏈結串列的頭節點插入到最小堆中。最小堆可以幫助我們快速地找到目前所有鏈結串列中的最小值節點。
2. 進行合併：從最小堆中取出最小值節點，將該節點接入結果鏈結串列，並將該節點的下一個節點繼續放入最小堆。這樣可以保證每次取出的節點都是當前所有節點中的最小值，從而保持鏈結串列的排序。
3. 處理空鏈結串列：當鏈結串列為空時，最小堆不會插入任何節點，結果鏈結串列的構建也會停止。

class Solution {
public:
    struct compare {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;

        // 將每個鏈結串列的頭節點加入最小堆
        for (ListNode* list : lists) {
            if (list != nullptr) {
                minHeap.push(list);
            }
        }

        ListNode dummy(0);
        ListNode* tail = &dummy;

        // 合併過程
        while (!minHeap.empty()) {
            ListNode* smallest = minHeap.top();
            minHeap.pop();
            tail->next = smallest;
            tail = tail->next;

            if (smallest->next != nullptr) {
                minHeap.push(smallest->next);
            }
        }

        return dummy.next;
    }
};

解法重點與分析

1. 最小堆（優先佇列）實現合併：本題關鍵在於如何高效地選出 k 個鏈結串列中的最小節點。通過最小堆可以保證每次取出的節點都是最小的，從而實現排序。
2. 空鏈結串列處理：如果輸入的鏈結串列是空的，則最小堆不會插入任何節點，結果鏈結串列最終為空，避免了無效操作。
3. 時間複雜度：每次將節點插入和取出最小堆的操作都需要 O(log k) 的時間，總共處理的節點數為 n，其中 n 是所有鏈結串列的總長度，因此總的時間複雜度為 O(n log k)。
4. 空間複雜度：最小堆最多存儲 k 個節點，因此空間複雜度為 O(k)。

總結

此題的主要挑戰在於如何高效地合併多個排序的鏈結串列。使用最小堆可以在每次選擇最小節點的過程中保證效率，最終構建出一個新的排序鏈結串列。時間複雜度為 O(n log k)，其中 n 是所有鏈結串列的總節點數，k 是鏈結串列的個數，這種解法在處理大量鏈結串列時表現出色。

以上是第十九天的自學內容分享，謝謝大家。